package cn.yza.算法.Leetcode;

/** 最小覆盖子串
 * @author Honglixi
 * @create 2021-12-10 20:01
 */
public class Leetcode76 {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }
        //表示当前滑动窗口中需要的各元素的数量
        int[] need = new int[128];
        //记录需要的字符的个数，字典的形式
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int l = 0; //左边界
        int r = 0; //右边界
        int size = Integer.MAX_VALUE; //当前窗口
        int count = t.length(); //需求的字符个数
        int start = 0; //最小覆盖子串开始的index

        //遍历所有字符
        while (r < s.length()) {
            char c = s.charAt(r);
            if (need[c] > 0) {
                count--;
            }
            need[c]--;
            //窗口中包含了所有需要的字符
            if (count == 0) {
                while (l < r && need[s.charAt(l)] < 0) { //此时左边界的是不需要的，需要左移
                    need[s.charAt(l)]++; //字典中的字符数加1
                    l++; //移动左边界
                }
                if (r - l + 1 < size) {
                    size = r - l + 1; //当前的最小窗口
                    start = l; //记录下最小值开始的位置
                }
                //l向右移动后窗口肯定不能满足了 就重新开始循环
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "":s.substring(start,start + size);
    }
}
